package com.breeze.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/linked-list-cycle/
 * 141 环形链表
 * 给定一个链表，判断链表中是否有环。
 * <p>
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 */
public class LeetCode141 {
    /**
     * 方法一：哈希表
     * <p>
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     */
    public boolean hasCycle(ListNode head) {
        // 存储的是每个节点的引用地址
        Set<ListNode> sets = new HashSet<>();
        while (head != null) {
            if (sets.contains(head)) {
                return true;
            }
            sets.add(head);
            head = head.next;
        }
        return false;
    }

    /**
     * 方法二：双指针，采用快慢指针
     * 思考：想象一下，两名运动员以不同的速度在环形赛道上匀速跑步会发生什么？ 答案就是相遇
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     */
    public boolean hasCycle1(ListNode head) {
        // 龟兔起跑
        ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null && fast.next != null) {
            // 龟走一步
            slow = slow.next;
            // 兔走两步
            fast = fast.next.next;
            // 两者只要相遇即为环，当然相遇不一定是环的起点
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public static void main(String[] args) {
        LeetCode141 leetCode141 = new LeetCode141();
        ListNode head = new ListNode(3);
        ListNode second = new ListNode(2);
        ListNode third = new ListNode(0);
        ListNode forth = new ListNode(-4);
        head.next = second;
        second.next = third;
        third.next = forth;
        forth.next = second;
        System.out.println(leetCode141.hasCycle1(head));
    }
}
